AUTHORS: T.Mekhaznia, A. Zidani, M. Derdour

Download as PDF

ABSTRACT: Cryptanalysis of modern cryptosystems is viewed as NP-Hard problem. Block ciphers, a modern symmetric key cipher are characterised with the nonlinearity and low autocorrelation of their structure. In literature, various attacks were accomplished based on traditional research algorithms such the brute force, but results still insufficient especially with wide instances due to resources requirement, which increase with the size of the problem. Actual research tends toward the use of bio-inspired intelligence algorithms, which are heuristic methods able to handle various combinatorial problems due to their optimisation of search space and fast convergence with reasonable resource consumption. The paper presents a new approach based on genetic algorithm for cryptanalysis of block ciphers; we focuses especially around the problem formulation, which seems a critical factor that depends the attack success. The experiments were accomplished on various set of data; the obtained results indicate that the proposed methodology seems an efficient tool in handling such attacks. Moreover, results comparisons of the considered approach with similar heuristics such Particle Swarm Optimisation and Brute Force reports its effectiveness in solving the considered problem.

KEYWORDS: Block ciphers; Genetic Algorithm; Particle swarm optimisation; Cryptanalysis; Bio-inspired intelligence.

REFERENCES:

[1] W. Stallings, Cryptography and Network Security, Netw. Secur., pp. 66–74, 2006.

[2] A. J. Menezes, P. C. Van Oorschot, and S. a. Vanstone, Handbook of Applied Cryptography, Electr. Eng., vol. 106, p. 780, 1997.

[3] K. V. S. Rao, M. R. Krishna, and D. Bujji Babu, Cryptanalysis of a Feistel Type Block Cipher by Feed Forward Neural Network Using Right Sigmoidal Signals, Int. J. Soft Comput., vol. 4, no. 3, pp. 131–135, 2009.

[4] F. L. Bauer, Decrypted Secrets: Methods and Maxims of Cryptology. Heidelberg: SpringerVerlag, 1997.

[5] E. Biham and A. Shamir, Diifferential Cryptanalysis of the Data Encryption Standard. Springer-Verlag, 1993.

[6] E. Biham and A. Shamir, Differential Cryptanalysis of the Full 16-round DES, in Advances in Cryptology — CRYPTO’ 92, 2001, pp. 487–496.

[7] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. Cryptol., vol. 4, no. 1, pp. 3–72, 1991.

[8] M. Matsui and Y. A, new method for known plaintext attack of feal cipher, Lect. Notes Comput. Sci., pp. 81–91, 1992.

[9] M. Matsui, The first experimental cryptanalysis of the data encryption standard, in 14th Annual International Cryptology Conference, 1994, pp. 1–11.

[10] M. Matsui, Linear Cryptanalysis Method for DES Cipher, LNCS, vol. 765, pp. 386–397, 1994.

[11] A. Biryukov and D. Wagner, Advances in Cryptology — EUROCRYPT 2000, in Lecture Notes in Computer Sciences, Springer Berlin Heidelberg, 2000, pp. 589–606.

[12] A. H. Gandomi and A. H. Alavi, Multi-stage genetic programming: A new strategy to nonlinear system modeling, Inf. Sci. (Ny)., vol. 181, no. 23, pp. 5227–5239, 2011.

[13] C. Blum and X. Li, Swarm Intelligence in Optimisation, Swarm Intell. Introd. Appl., pp. 43–85, 2008.

[14] T. S. C. Felix and K. T. Manoj, Swarm Intelligence, Focus on Ant and Particle Swarm Optimization, in Numerical Analysis and Scientific Computing, T. S. C. Felix and K. T. Manoj, Eds. I-Tech Education and Publishing, 2007.

[15] T. M. R. Sharvani.G.S, N.K. Cauvery, Different Types of Swarm Intelligence Algorithm for Routing, in 2009 International Conference on Advances in Recent Technologies in Communication and Computing, 2009, pp. 604–609.

[16] H. Feistel, Cryptography and Computer Privacy, Scientific American, vol. 228, no. 5. pp. 15–23, 1973.

[17] B. Schneier, The Blowfish Encryption Algorithm, Dr. Dobbs J., vol. 23, pp. 38–40, 1998.

[18] H. Feistel, Block cipher cryptographic system, #3 798 359, 1974.

[19] A. Carlisle, Constructing of Symmetric ciphers using the CAST design Procedure,” Des. Codes, Cryptogr., vol. 12, pp. 283–316, 1997.

[20] National Bureau Of Standards, Data Encryption Standard (DES), Technology, vol. 46–3, no. 46, pp. 1–26, 1999.

[21] X. Lai and J. L. Massey, A proposal for a new block encryption standard, Adv. Cryptology—EUROCRYPT’90, pp. 389–404, 2006.

[22] R. L. Rivest, The RC5 Encryption Algorithm, Technology, vol. 1008, pp. 86– 96, 1995.

[23] A. Shimizu and S. Miyaguchi, Fast Data Encipherment Algorithm FEAL, in Advances in Cryptology — EUROCRYPT ’87, 1988, vol. 304, pp. 267–278.

[24] S. Heron, Advanced Encryption Standard (AES), Netw. Secur., vol. 2009, no. 12, pp. 8–12, Dec. 2009.

[25] W. S. McCulloch and W. Pitts, A logical calculus of the ideas immanent in nervous activity, Bull. Math. Biophys., vol. 5, no. 4, pp. 115–133, 1943.

[26] P. Tarasewich and P. R. McMullen, Swarm intelligence: power in numbers, Commun. ACM, vol. 45, no. August, pp. 62–67, 2002.

[27] E. Bonabeau, M. Dorigo, and G. Theraulaz, From Natural to Artificial Swarm Intelligence. Oxford University Press, 1999.

[28] L. M. Hiot, Y. S. Ong, B. K. Panigrahi, Y. Shi, M.-H. Lim, P. K. Tripathi, S. Bandyopadhyay, and S. K. Pal, Handbook of Swarm Intelligence, vol. 8. 2010.

[29] M. Dorigo, V. Maniezzo, and A. Colorni, Positive feedback as a search strategy, Tech. Rep. 91-016, 1991.

[30] K. M. Passino, Biomimicry of bacterial foraging for distributed optimization and control, Control Systems, IEEE, vol. 22, no. 3. pp. 52–67, 2002.

[31] D. F. Signorini and J. M. Slattery, Neural networks., Lancet (London, England), vol. 346, no. 8988, p. 1500, Dec. 1995.

[32] S.-C. Chu, P.-W. Tsai, and J.-S. Pan, Cat swarm optimization, PRICAI 2006 Trends Artif. Intell., pp. 854–858, 2006.

[33] M. Bakhouya and J. Gaber, An Immune Inspired-based Optimization Algorithm: Application to the Traveling Salesman Problem, vol. 9, no. 1, pp. 105–116, 2007.

[34] K. N. Krishnanand and D. Ghose, Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions, Swarm Intell., vol. 3, no. 2, pp. 87–124, 2009.

[35] X. S. Yang, A new metaheuristic Batinspired Algorithm, Stud. Comput. Intell., vol. 284, pp. 65–74, 2010.

[36] S. Mirjalili, S. M. Mirjalili, and A. Lewis, Grey Wolf Optimizer, Adv. Eng. Softw., vol. 69, pp. 46–61, 2014.

[37] R. E. Perez and K. Behdinan, Particle swarm approach for structural design optimization, Comput. Struct., vol. 85, no. 19–20, pp. 1579–1588, 2007.

[38] P. Pongchairerks, Particle swarm optimization algorithm applied to scheduling problems, ScienceAsia, vol. 35, no. 1, pp. 89–94, 2009.

[39] G. Hanrahan, Swarm intelligence metaheuristics for enhanced data analysis and optimization., Analyst, vol. 136, no. 18, pp. 3587–94, 2011.

[40] D. E. Goldberg and J. H. Holland, Genetic Algorithms and Machine Learning, Mach. Learn., vol. 3, no. 2, pp. 95–99, 1988.

[41] A. P. Engelbrecht, Fundamentals of Computational Swarm Intelligence, vol. 8. Wiley, 2005.

[42] J. A. Clark, J. L. Jacob, and S. Stepney, The design of S-boxes by simulated annealing, New Gener. Comput., vol. 23, no. 3, pp. 219–231, 2005.

[43] J. Olamaei, T. Niknam, and G. Gharehpetian, Application of particle swarm optimization for distribution feeder reconfiguration considering distributed generators, Appl. Math. Comput., vol. 201, no. 1–2, pp. 575– 586, 2008.

[44] J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, vol. 1, no. 1. 1975.

[45] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.

[46] M. D. Vose and A. Hall, Modeling Simple Genetic Algorithms, Evol. Comput., vol. 3, no. 4, pp. 453–472, 1996.

[47] J. H. HOLLAND, Adaptation in natural and artificial systems. MIT Press, 1992.

[48] L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence through Simulated Evolution, Wiley, no. 1965, pp. 27–38, 1997.

[49] I. F. Gonos, N. E. Mastorakis, S. Member, M. N. S. Swamy, and L. Fellow, A Genetic Algorithm Approach to the Problem of Factorization of General Multidimensional Polynomials, vol. 50, no. 1, pp. 16–22, 2003.

[50] D. B. Fogel, Evolutionary algorithms in theory and practice, Complexity, vol. 2, no. 4, pp. 26–27, Mar. 1997.

[51] C. W. Ahn, Practical genetic algorithms, vol. 18. 2006.

[52] Z. Michalewicz, Genetic algorithms + data structures = evolution programs (3rd ed.), vol. 1. 1996.

[53] K. F. Man, K. S. Tang, and S. Kwong, Genetic algorithms: Concepts and applications, IEEE Trans. Ind. Electron., vol. 43, no. 5, pp. 519–534, 1996.

[54] R. Matthews, The use of genetic algorithms in cryptanalysis, Cryptologia, 1993.

[55] H. M. H. Husei, B. I. Bayoumi, F. S. Holail, B. E. M. Hasan, and M. Z. Abd El-Mageed, A genetic algorithm for cryptanalysis with application to DES-like systems, Int. J. Netw. Secur., vol. 8, no. 2, pp. 177–188, 2009.

[56] A. G. Bafghi and B. Sadeghiyan, Finding suitable differential characteristics for block ciphers with Ant colony technique, in Ninth International Symposium on Computers and Communications, 2004. Proceedings. ISCC 2004, 2004, vol. 1, pp. 418–423 Vol.1.

[57] E. C. Laskari, G. C. Meletiou, Y. C. Stamatiou, and M. N. Vrahatis, Cryptography and cryptanalysis through computational intelligence, Stud. Comput. Intell., vol. 57, pp. 1–49, 2007.

[58] E. C. Laskari, G. C. Meletiou, Y. C. Stamatiou, and M. N. Vrahatis, Applying evolutionary computation methods for the cryptanalysis of Feistel ciphers, Appl. Math. Comput., vol. 184, no. 1, pp. 63–72, 2007.

[59] E. C. Laskari, G. C. Meletiou, Y. C. Stamatiou, and M. N. Vrahatis, Evolutionary computation based cryptanalysis: A first study, Nonlinear Anal. Methods Appl., vol. 63, no. 5–7, pp. E823–E830, 2005.

[60] J. Song, H. Zhang, Q. Meng, and Z. Wang, Cryptanalysis of four-round des based on genetic algorithm, 2007 Int. Conf. Wirel. Commun. Netw. Mob. Comput. WiCOM 2007, pp. 2326–2329, 2007.

[61] N. Nalini and G. Raghavendra Rao, Attacks of simple block ciphers via efficient heuristics, Inf. Sci. (Ny)., vol. 177, pp. 2553–2569, 2007.

[62] P. Garg, S. Varshney, and M. Bhardwaj, Cryptanalysis of Simplified Data Encryption Standard using Genetic Algorithm, Am. J. Networks Commun., vol. 4, no. 3, pp. 32–36, 2015.

[63] Y. Fan, S. Jun, and Z. Huanguo, Quantitative cryptanalysis of six-round DES using Evolutionary computation, in Third Internationa Symposium, ISICA, 2008, pp. 134–141.

[64] W. Shahzad, A. B. Siddiqui, and F. A. Khan, Cryptanalysis of Four-Rounded DES using Binary Particle Swarm Optimization, Simulation, pp. 1757–1758, 2009.

[65] R. Vimalathithan and M. L. Valarmathi, Cryptanalysis of Simplified-DES using Computational Intelligence, WSEAS Trans. Comput., vol. 10, no. 7, pp. 210–219, 2011.

[66] S. Pandey and P. M. Mishra, Particle Swarm Optimization in Cryptanalysis of DES, Int. J. Adv. Res. Comput. Eng. Technol., vol. 1, no. 4, pp. 379–381, 2012.

[67] R. Vimalathithan and M. Valarmathi, Cryptanalysis of Simplified-AES using Particle Swarm Optimisation, Def. Sci. J., vol. 62, no. 2, pp. 117–121, 2012.

[68] S. A. A. Hamdani, S. Shafiq, and Farrukh Aslam Khan, Cryptanalysis of FourRounded DES Using Binary Artificial Immune System, in Lecture Notes in Computer Scienc, Y. T. Ytan, Y. Sh, and T. Kay Chen, Eds. Springer Berlin Heidelberg, 2010, pp. 338–346.

[69] S. Khan, W. Shahzad, and F. A. Khan, Cryptanalysis of four-rounded DES using ant colony optimization, 2010 Int. Conf. Inf. Sci. Appl. ICISA 2010, pp. 2161–2166, 2010.

[70] W. G. Abd-Elmonim, N. I. Ghali, A. E. Hassanien, and A. Abraham, Knownplaintext attack of DES-16 using particle swarm optimization, Proc. 2011 3rd World Congr. Nat. Biol. Inspired Comput. NaBIC 2011, pp. 12–16, 2011.

[71] S. S. Jadon, H. Sharma, E. Kumar, and J. C. Bansal, Application of binary particle swarm optimization in cryptanalysis of DES, Adv. Intell. Soft Comput., vol. 130 AISC, no. VOL. 1, pp. 1061–1071, 2012.

[72] R. Vimalathithan and M. Valarmathi, Cryptanalysis of DES using Computational Intelligence, WSEAS Trans. Comput., vol. 55, no. 2, pp. 237–244, 2011.

[73] F. Teytaud and C. Fonlupt, A Critical Reassessment of Evolutionary Algorithms on the cryptanalysis of the simplified data encryption standard algorithm, arXiv Prepr. arXiv1407.1993, p. 12, 2014.

[74] C. De Canniere, A. Biryukov, and B. Preneel, An introduction to Block Cipher Cryptanalysis, Proc. IEEE, vol. 94, no. 2, pp. 346–356, 2006.

[75] D. Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, IBM Journal of Research and Development, vol. 38, no. 3. pp. 243–250, 1994.

[76] P. Isasi and J. C. Hernandez, Introduction to the Applications of Evolutionary Computation in Computer Security and Cryptography, Comput. Intell., vol. 20, no. 3, pp. 445–449, Aug. 2004.

[77] D. G. N. Hunter and A. R. McKenzie, Experiments with Relaxation Algorithms for Breaking Simple Substitution Ciphers, Comput. J., vol. 26, no. 1, pp. 68–71, 1983.

[78] J. Kennedy and R. Eberhart, Particle swarm optimization, Proc. ICNN’95 - Int. Conf. Neural Networks, vol. 4, pp. 1942–1948, 1995.

[79] R. . Eberhart, P. Simpson, and R. Dobbins, Computational Intelligence PC Tools. Academic Press, 1996.

[80] Y. Shi and R. C. Eberhart, Empirical study of particle swarm optimization, Proc. 1999 Congr. Evol. Comput., pp. 1945–1950, 1999.

[81] M. Zambrano-Bigiarini, M. Clerc, and R. Rojas, Standard Particle Swarm Optimisation 2011 at CEC-2013: A baseline for future PSO improvements, in 2013 IEEE Congress on Evolutionary Computation, 2013, pp. 2337–2344.

[82] D. Bratton and T. Blackwell, A Simplified Recombinant PSO, J. Artif. Evol. Appl., vol. 2008, no. 1, pp. 1–10, 2008.

[83] M. Meissner, M. Schmuker, and G. Schneider, Optimized Particle Swarm Optimization (OPSO) and its application to artificial neural network training., BMC Bioinformatics, vol. 7, p. 125, 2006.

[84] W. J. Zhang and X. F. Xie, DEPSO: Hybrid Particle Swarm with Differential Evolution Operators, Proc. 2003 IEEE Int. Conf. Syst. Man Cybern., vol. 4, no. 1, pp. 3816–3821, 2003.

[85] Z. H. Zhan, J. Zhang, Y. Li, and H. S. H. Chung, Adaptive Particle Swarm Optimization, IEEE Trans. Syst. Man Cybern. Part B-Cybernetics, vol. 39, no. 6, pp. 1362–1381, 2009.

[86] J. Salerno, Using the particle swarm optimization technique to train a recurrent neural model, in Proceedings Ninth IEEE International Conference on Tools with Artificial Intelligence, 1997, pp. 45–49.

[87] J. Kennedy, R. C. Eberhart, and Y. Shi, Swarm Intelligence, Swarm Intell., pp. 287– 325, 2001.

[88] E. H. Luna, C. A. C. Coello, and A. H. Aguirre, On the use of a population-based particle swarm optimizer to design combinational logic circuits, in 2004 NASA/DoD Conference on Evolvable Hardware, 2004. Proceedings, 2004, pp. 183–190.

[89] X. Hu, R. C. Eberhart, and Y. Shi, Engineering optimization with particle swarm, Swarm Intelligence Symposium, 2003. SIS ’03. Proceedings of the 2003 IEEE. pp. 53–57, 2003.

[90] H. Yoshida, K. Kawata, Y. Fukuyama, S. Takayama, and Y. Nakanishi, A particle swarm optimization for reactive power and voltage control considering voltage security assessment, IEEE Trans. Power Syst., vol. 15, no. 4, pp. 1232–1239, 2000.

[91] J. Robinson and Y. Rahmat-Samii, Particle swarm optimization in electromagnetics, Antennas Propagation, IEEE Trans., vol. 52, no. 2, pp. 397–407, 2004.

[92] M. F. Uddin and a. M. Youssef, Cryptanalysis of Simple Substitution Ciphers Using Particle Swarm Optimization, 2006 IEEE Int. Conf. Evol. Comput., pp. 677–680, 2006.

[93] N. Nalini and G. Raghavendra Rao, Cryptanalysis of block ciphers via improvised particle swarm optimization and extended simulated annealing techniques, Int. J. Netw. Secur., vol. 6, no. 3, pp. 342– 353, 2008.

[94] K. Dworak and U. Boryczka, Cryptanalysis of SDES Using Modified Version of Binary Particle Swarm Optimization, in Computational Collective Intelligence, vol. 9330, Springer International Publishing, 2015, pp. 159–168.

[95] G. Nelson, S. Wallis, and B. Aarts, Exploring Natural Language, vol. G29. Amsterdam: John Benjamins Publishing Company, 2002.

[96] E. Schaefer, A Simplified {D}ata {E}ncryption {S}tandard Algorithm, Cryptologia, vol. 20, no. 1, pp. 77–84, 1996.

[97] B. den BOER, Cryptanalysis of {F.E.A.L.}, in Advances in Cryptology. EUROCRYPT’88, vol. 330.

[98] H. Gilbert and G. Chassé, A Statistical Attack of the FEAL-8 Cryptosystem, in Advances in Cryptology-CRYPT0’ 90. Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1990, pp. 22–33.

[99] K. Ohta and K. Aoki, Linear cryptanalysis of the fast data encipherment algorithm, Adv. Cryptology—Crypto’94, pp. 12–16, 1994.

[100] M. Matsui and A. Yamagishi, A New Method for Known Plaintext Attack of FEAL Cipher, in Advances in Cryptology — EUROCRYPT’ 92, 1993, vol. 658, pp. 81– 91.

[101] E. Biham and A. Shamir, Differential Cryptanalysis of Feal and N-Hash, 547, pp. 1–16, 1991.

[102] L. R. Knudsen and W. Meier, Improved Differential Attacks on RC5, in Advances in Cryptology CRYPTO’96, 1996, pp. 216–228.

[103] A. Biryukov and E. Kushilevitz, Improved cryptanalysis of RC5, Finland, 1998, pp. 85– 99.